package algorithms.sort;

import static algorithms.Util.exchange;
import static algorithms.Util.generateArray;
import static algorithms.Util.print;

/**
 * <h4>快速排序</h4>
 * <h5>基本思想是：</h5>
 * <li>1．先从数列中取出一个数作为基准数。</li>
 * <li>2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。</li>
 * <li>3．再对左右区间重复第二步，直到各区间只有一个数。</li>
 * <h5>平均时间复杂度：O(N*logN)</h5>
 * 
 * @author shaoyuxia
 *
 * @param <T>
 */
public class QuickSort<T extends Comparable<T>> implements ISort<T> {

	@Override
	public T[] sort(T[] a) {
		int left = 0, right = a.length - 1;
		recursiveAdjust(a, left, right);
		return a;
	}

	int ajustArray(T[] a, int leftborder, int rightborder) {
		int base = leftborder, left = leftborder, right = rightborder;

		while (left < right) {
			// 自后往前扫描
			for (; right > base; right--) {
				// 在右侧发现比基数小的数
				if (a[right].compareTo(a[base]) < 0) {
					exchange(a, base, right);
					base = right;
					break;
				}
			}
			// 自前往后扫描
			for (; left < base; left++) {
				// 在左侧发现比基数大的数
				if (a[left].compareTo(a[base]) > 0) {
					exchange(a, base, left);
					base = left;
					break;
				}
			}
		}
		return base;
	}

	void recursiveAdjust(T[] a, int left, int right) {
		if (left < right) {
			int base = ajustArray(a, left, right);
			recursiveAdjust(a, left, base - 1);
			recursiveAdjust(a, base + 1, right);
		}
	}

	public static void main(String[] args) {
		QuickSort<Integer> sort = new QuickSort<>();
		Integer[] a = generateArray(50000);
		print(a, 30);
		int left = 0, right = a.length - 1;
		sort.recursiveAdjust(a, left, right);

		// int base = 0, left = 0, right = a.length - 1;
		// while (left < right) {
		// for (; right > left; right--) {
		// if (a[base] > a[right]) {
		// Util.exchange(a, base, right);
		// base = right;
		// break;
		// }
		// }
		// for (; left < right; left++) {
		// if (a[base] < a[left]) {
		// Util.exchange(a, base, left);
		// base = left;
		// break;
		// }
		// }
		// }
		// System.out.println("base:" + base);
		print(a, 300);
	}
}
